package explore.jqq.list;

import java.util.Arrays;

import static java.lang.Math.max;
//以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
//    请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。


public class MergeInterval {
    public static void main(String[] args) {
        explore.jqq.list.MergeInterval mergeInterval = new explore.jqq.list.MergeInterval();
        int[][] Interval = new int[][]{{2,3},{4,5},{6,7},{8,9},{1,10}};
//        Interval = mergeInterval.sorted(Interval);
        int[][] i = mergeInterval.merge(Interval);
        System.out.println(Arrays.deepToString(i));
        }

    public int[][] sorted(int[][] intervals){
        for(int i=0;i< intervals.length-1;i++){
            for(int j=0;j<intervals.length-i-1;j++) {
                if (intervals[j][0] > intervals[j + 1][0]) {
                    int[] temp = intervals[j];
                    intervals[j] = intervals[j + 1];
                    intervals[j + 1] = temp;
                }
            }
        }
        return intervals;
    }

    public int[][] merge(int[][] intervals) {
        intervals = sorted(intervals);
        int[][] temp =new int[intervals.length][2];
        temp[0]=intervals[0];
        int temp_len = 0;
        for(int i=1;i< intervals.length;i++){
            for(int m=0;m<=temp_len;m++){
                if(IsOverlapping(temp[m],intervals[i]) || IsOverlapping(intervals[i],temp[m])){
                    temp[m] = new int[]{Math.min(temp[m][0], intervals[i][0]), Math.max(temp[m][1], intervals[i][1])};
                    break;
                }
                if(m == temp_len) {
                    temp[temp_len + 1] = intervals[i];
                    temp_len++;
                }
            }
        }
        int [][] result = new int[temp_len+1][2];
        for(int j=0;j<temp_len+1;j++){
            result[j] = temp[j];
        }
        return result;
    }

    public boolean IsOverlapping(int[] a,int[] b){
        if((a[0]<=b[1] && a[1]>=b[1]) || (a[0]<=b[0] && a[1]>=b[0])){
            return true;
        }else {
            return false;
        }
    }
}
